package tree_backtrack_prune;

import java.util.*;


/**
 * 看图：
 * https://leetcode-cn.com/problems/combination-sum/solution/shou-hua-tu-jie-zu-he-zong-he-combination-sum-by-x/
 * 什么时候用used数组 什么时候用sum  ：
 * https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
 *
 */
class 组合总和_39_重做版 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0 , 0);
        return res;
    }

    private void dfs(int[] candidates, int target, int sum, int begin) {
        if(sum > target) return;
        if(sum == target) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        for(int i = begin; i< candidates.length; i++) {

            tmp.add(candidates[i]);
            // i = begin 可以从 begin再次遍历  因此可以一直取begin 向下递归 因此 最后一个入参是i
            // 如果不能重复取数 就用 i+ 1
            dfs(candidates, target, sum + candidates[i], i);
            tmp.remove(tmp.size() -1);
        }
    }
}

/**
 *
 * https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
 * 回溯剪枝 问题
 * 回溯：
 *      for循环中  stack先addLast
 *                      在removeLast  换下一个来试试
 * 剪枝：
 *      1. < 0 的终止条件移到for循环中  提前结束不必要的for
 *      2. 每次回溯进入的时候   i增加  避免成为指数级问题
 * 全排列 46 全组合 39  求法
 */
class 组合总和_39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> branch = new ArrayDeque<>();
        Arrays.sort(candidates);
        dfs(candidates, target, 0, branch, res);
        return res;
    }

    private void  dfs(int[] candidates, int remain, int begin, Deque<Integer> branch, List<List<Integer>> res) {
        // 判断是不是满足条件了 不用继续递归
        // 恰好总数相等
        if(remain == 0) {
            //  复制一份  否则最后指针引用全为空
            res.add(new ArrayList<>(branch));
        }
        // 在这里 < 0 判断 可以移到for循环中  用于剪枝
        // 因 candidates 是有序的
        // 后面的更大   退回到上一层  都不用removeLast 继续for循环了   后面都一样的
        /*if(remain < 0) {
            return;
        }*/

        for(int i = begin; i < candidates.length; i++) {
            if(remain < 0) {
                break;
            }
            branch.addLast(candidates[i]);
            // 剪枝  前面的不能用  但是可以用自身第i个数据  因此从i开始
            dfs(candidates, remain - candidates[i], i, branch, res);
            branch.removeLast();
        }
    }




    public static int strStr(String haystack, String needle) {
        char[] str = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        if (pattern.length == 0) {
            return 0;
        }
        if (str.length == 0 || str.length < pattern.length) {
            return -1;
        }
        int hashsum = 0;
        for(char c : pattern) {
            hashsum += (c - 'a');
        }
        int sum = 0;
        for(int i = 0; i< pattern.length; i++) {
            sum += (str[i] - 'a');
        }
        if(hashsum == sum && equals(str, pattern, pattern.length - 1)) return 0;
        System.out.println(hashsum + "---" + sum);
        for(int i = pattern.length; i < str.length; i++) {
            sum = sum + (str[i] - 'a') - (str[i - pattern.length] - 'a');
            if(sum == hashsum) {
                if (equals(str, pattern, i)) return i - pattern.length + 1;

            }
        }
        return -1;
    }

    private static boolean equals(char[] str, char[] pattern, int i) {
        int j = 0;
        while(j< pattern.length) {
            if(str[i- pattern.length + j + 1] != pattern[j]) {
                break;
            }
            j ++;
        }
        System.out.println(j);
        if(j == pattern.length) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        strStr("mississippi","sipp");
    }
}